#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>



int main() 
{

    std::string source;
    // std::cin >> source;
    source = "A blockhouse is a small castle that has four openings through which to shoot.";
    // 1. 转化为小写 并且进行切分
    size_t left = 0;
    size_t right = 0;
    std::vector<std::string> tmp;
    while(right != source.length())
    {
        if(source[right] < 91 && source[right] > 64)
        {
            source[right] = source[right] + 32;
        }
        if(source[right] == ' ' || source[right] == '.')
        {
            tmp.push_back(source.substr(left, right - left));
            left = right + 1;
        }
        ++right;
    }
    // 2. 使用map进行排序
    std::map<std::string, int> dict;
    for (std::string& word : tmp)
    {
        if (dict.end() != dict.find(word))
        {
            // 存在于dict中
            ++dict[word];
        }
        else
        {
           dict[word] = 1;
        }
    }
    // sort(dict.begin(), dict.end());
    // 没法对map进行直接排序的 只能借助vector
    std::vector<std::pair<std::string, int>> result(dict.begin(), dict.end());
    std::sort(result.begin(), result.end(), [](const std::pair<std::string, int>& a, const std::pair<std::string, int>& b) {
        if (a.second != b.second)
            return (a.second) > (b.second);
        else
            return (a.first) < (b.first);
        });
    // 3. 打印
    for(const auto& item : result)
    {
        std::cout << item.first << ":" << item.second << std::endl;
    }
    return 0; 
}
// 64 位输出请用 printf("%lld")



// using namespace std;
// class Solution {
// public:
//     vector<string> topKFrequent(vector<string>& words, int k) {
//         unordered_map<string, int> dict;
//         for(string& word : words)
//         {
//             if(dict.end() != dict.find(word))
//             {
//                 // 存在于dict中
//                 ++dict[word];
//             }
//             else
//             {
//                 dict[word] = 1;
//             }
//         }
//         sort(dict.begin(), dict.end());
//         // sort(dict.begin(), dict.end(), [](const pair<string, int>& a, const pair<string, int>& b){
//         //     return a.second > b.second;
//         // });
//         vector<string> result;
//         for(const auto& item : dict)
//         {
//             result.push_back(item.first);
//         }
//         return result;
//     }
// };

// int main()
// {
//     Solution s;
//     vector<string> x;
//     x.push_back("123");
//     x.push_back("123");
//     x.push_back("465");
//     x.push_back("456");
//     x.push_back("123");
//     x.push_back("123");
//     x.push_back("123");
//     s.topKFrequent(x, 5);
//     return 0;
// }

// int main()
// {
//     std::map<std::string, int> map;
//     // pair的使用不需要额外引头文件
//     map.insert(std::pair<std::string, int>("pangchao", 123));
//     map.insert(std::pair<std::string, int>("liqing", 456));
//     map.insert(std::pair<std::string, int>("heqing", 789));
//     map["wanger"] = 159;
//     std::map<std::string, int>::iterator it = map.begin();
//     while(it != map.end())
//     {
//         std::cout << it->first << ": " << it->second << std::endl;
//         ++it;
//     }
//     std::cout << "size: " << map.size() << std::endl;
//     std::cout << "empty: " << map.empty() << std::endl;

//     return 0;
// }




// bool func(int a, int b)
// {
//     return a > b;
// }

// int main()
// {
//     // 函数指针 传入递减的函数指针 --->
//     std::set<int, bool(*)(int, int)> set(func);
//     set.insert(1);
//     set.insert(1);
//     set.insert(2);
//     set.insert(3);
//     set.insert(4);
//     std::set<int>::iterator it = set.begin();
//     while(it != set.end())
//     {
//         std::cout << *it << " " ;
//         ++it;
//     }
//     std::cout << std::endl;

//     return 0;
// }